package com.nlp.algorithm.greedy;

public class RemoveK {
	/**
	 * 
	 * 像这样一次求得【局部最优解】，最终的【全局最优解的】思想叫做，【贪心算法】
	 * 删除k的数，使得得到的数字最小
	 * @param k
	 * @param num
	 */
	public static void remove(int k, String num) {
		
		for (int i = 0; i < k; i++) {
			boolean cut = false;
			for (int j = 0; j < num.length() - 1; j++) {
				if (num.charAt(j) > num.charAt(j+1)) {
					num = num.substring(0, j) + num.substring(j+1	,num.length());
					cut = true;
					break;
				}
			}
			//如果没有删除，则删除末尾的数
			if (!cut) {
				num = num.substring(0, num.length()-1);
			}
			for (int j = 0; j < num.length()-1; j++) {
				if (num.charAt(0) != '0') {
					break;
				}
				num = num.substring(1, num.length());
			}
		}
		if (num.length() == 0) {
			num = "0";
		}
		System.out.println(num);
	}
	
	public static void main(String[] args) {
		remove(2, "9561424");
	}
}
